from typing import List

from sortedcontainers import SortedList


class Solution:
    _MOD = 10 ** 9 + 7

    def numsGame(self, nums: List[int]) -> List[int]:
        size = len(nums)

        ans = []

        differs = SortedList()  # 与从1开始的等差数列的差值（实际值-期望值）
        sum_differ = 0  # 差值总和
        left, right = float("inf"), float("-inf")  # 最小差值和最大差值（用于二分查找作为两侧边界）
        for i in range(size):
            num = i + 1  # 当前数列中已包含的数

            # ----- 处理当前值与从1开始的等差数列的期望值 -----
            expect = i + 1  # 从1开始的等差数列的期望值
            differ = nums[i] - expect  # 差值：实际值-期望值
            differs.add(differ)
            sum_differ += differ
            left, right = min(left, differ), max(right, differ)

            # ----- 二分查找寻找最优实际差值 -----
            choose_differ = None  # 最优实际差值变量
            l, r = left, right
            while l < r:
                m = (l + r) // 2
                lower_num = differs.bisect_left(m)  # 小于mid的有num1个
                upper_num = (i + 1) - differs.bisect_right(m)  # 大于mid的有num3个
                if lower_num > upper_num:
                    r = m
                elif lower_num < upper_num:
                    l = m + 1  # 因为这里加1，所以结果可能是min_differ-1或min_differ
                else:
                    choose_differ = m
                    break

            if choose_differ is None:
                maybe_differ = [l - 1, l]
                maybe_differ.sort(key=lambda x: abs(differs.bisect_left(x)) + abs(size - differs.bisect_right(x)))
                choose_differ = maybe_differ[0]

            # ----- 计算最终结果 -----
            print(differs, choose_differ, "->", abs(sum_differ - choose_differ * num))
            ans.append(abs(sum_differ - choose_differ * num))

        return ans


if __name__ == "__main__":
    print(Solution().numsGame([3, 4, 5, 1, 6, 7]))  # [0,0,0,5,6,7]
    print(Solution().numsGame([1, 2, 3, 4, 5]))  # [0,0,0,0,0]
    print(Solution().numsGame([1, 1, 1, 2, 3, 4]))  # [0,1,2,3,3,3]
